 /*******************************************************************************
  * Copyright (c) 2007 Wind River Systems, Inc. and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * Martin Oberhuber (Wind River) - initial API and implementation for [105554]
  *******************************************************************************/

 package org.eclipse.core.internal.localstore;

 import java.util.Arrays ;

 /**
  * A pool of Strings for doing prefix checks against multiple
  * candidates.
  * <p>
  * Allows to enter a list of Strings, and then perform the
  * following checks:
  * <ul>
  * <li>{@link #containsAsPrefix(String)} - check whether a given
  * String s is a prefix of any String in the pool.</li>
  * <li>{@link #hasPrefixOf(String)} - check whether any String
  * in the pool is a prefix of the given String s.
  * </ul>
  * The prefix pool is always kept normalized, i.e. no element of
  * the pool is a prefix of any other element in the pool. In order
  * to maintain this constraint, there are two methods for adding
  * Strings to the pool:
  * <ul>
  * <li>{@link #insertLonger(String)} - add a String s to the pool,
  * and remove any existing prefix of s from the pool.</li>
  * <li>{@link #insertShorter(String)} - add a String s to the pool,
  * and remove any existing Strings sx from the pool which
  * contain s as prefix.</li>
  * </ul>
  * The PrefixPool grows as needed when adding Strings. Typically,
  * it is used for prefix checks on absolute paths of a tree.
  * </p><p>
  * This class is not thread-safe: no two threads may add or
  * check items at the same time.
  *
  * @since 3.3
  */
 public class PrefixPool {
     private String [] pool;
     private int size;

     /**
      * Constructor.
      * @param initialCapacity the initial size of the
      * internal array holding the String pool. Must
      * be greater than 0.
      */
     public PrefixPool(int initialCapacity) {
         if (initialCapacity <= 0)
             throw new IllegalArgumentException ("Illegal Capacity: " + initialCapacity); //$NON-NLS-1$
 pool = new String [initialCapacity];
         size = 0;
     }

     /**
      * Clears the prefix pool, allowing all items to be
      * garbage collected. Does not change the capacity
      * of the pool.
      */
     public/*synchronized*/void clear() {
         Arrays.fill(pool, 0, size, null);
         size = 0;
     }

     /**
      * Return the current size of prefix pool.
      * @return the number of elements in the pool.
      */
     public/*synchronized*/int size() {
         return size;
     }

     /**
      * Ensure that there is room for at least one more element.
      */
     private void checkCapacity() {
         if (size + 1 >= pool.length) {
             String [] newprefixList = new String [2 * pool.length];
             System.arraycopy(pool, 0, newprefixList, 0, pool.length);
             Arrays.fill(pool, null); //help the garbage collector
 pool = newprefixList;
         }
     }

     /**
      * Insert a String s into the pool of known prefixes, removing
      * any existing prefix of it.
      * <p>
      * If any existing prefix of this String is found in the pool,
      * it is replaced by the new longer one in order to maintain
      * the constraint of keeping the pool normalized.
      * </p><p>
      * If it turns out that s is actually a prefix or equal to
      * an existing element in the pool (so it is essentially
      * shorter), this method returns with no operation in order
      * to maintain the constraint that the pool remains normalized.
      * </p>
      * @param s the String to insert.
      */
     public/*synchronized*/void insertLonger(String s) {
         //check in reverse order since we expect some locality
 for (int i = size - 1; i >= 0; i--) {
             if (pool[i].startsWith(s)) {
                 //prefix of an existing String --> no-op
 return;
             } else if (s.startsWith(pool[i])) {
                 //replace, since a longer s has more prefixes than a short one
 pool[i] = s;
                 return;
             }
         }
         checkCapacity();
         pool[size] = s;
         size++;
     }

     /**
      * Insert a String s into the pool of known prefixes, removing
      * any Strings that have s as prefix.
      * <p>
      * If this String is a prefix of any existing String in the pool,
      * all elements that contain the new String as prefix are removed
      * and return value <code>true</code> is returned.
      * </p><p>
      * Otherwise, the new String is added to the pool unless an
      * equal String or e prefix of it exists there already (so
      * it is essentially equal or longer than an existing prefix).
      * In all these cases, <code>false</code> is returned since
      * no prefixes were replaced.
      * </p>
      * @param s the String to insert.
      * @return <code>true</code>if any longer elements have been
      * removed.
      */
     public/*synchronized*/boolean insertShorter(String s) {
         boolean replaced = false;
         //check in reverse order since we expect some locality
 for (int i = size - 1; i >= 0; i--) {
             if (s.startsWith(pool[i])) {
                 //longer or equal to an existing prefix - nothing to do
 return false;
             } else if (pool[i].startsWith(s)) {
                 if (replaced) {
                     //replaced before, so shrink the array.
 //Safe since we are iterating in reverse order.
 System.arraycopy(pool, i + 1, pool, i, size - i - 1);
                     size--;
                     pool[size] = null;
                 } else {
                     //replace, since this is a shorter s
 pool[i] = s;
                     replaced = true;
                 }
             }
         }
         if (!replaced) {
             //append at the end
 checkCapacity();
             pool[size] = s;
             size++;
         }
         return replaced;
     }

     /**
      * Check if the given String s is a prefix of any of Strings
      * in the pool.
      * @param s a s to check for being a prefix
      * @return <code>true</code> if the passed s is a prefix
      * of any of the Strings contained in the pool.
      */
     public/*synchronized*/boolean containsAsPrefix(String s) {
         //check in reverse order since we expect some locality
 for (int i = size - 1; i >= 0; i--) {
             if (pool[i].startsWith(s)) {
                 return true;
             }
         }
         return false;
     }

     /**
      * Test if the String pool contains any one that is a prefix
      * of the given String s.
      * @param s the String to test
      * @return <code>true</code> if the String pool contains a
      * prefix of the given String.
      */
     public/*synchronized*/boolean hasPrefixOf(String s) {
         for (int i = size - 1; i >= 0; i--) {
             if (s.startsWith(pool[i])) {
                 return true;
             }
         }
         return false;
     }

 }

